#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<windows.h> 
#include <string.h>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include <iostream>
//using namespace std;
//const int N = 10010;
//int num[N];
//int t, b;
//void quick(int num[], int l, int r)
//{
//    if (l >= r)return;
//    int x = num[(l + r) / 2];
//    int i = l - 1, j = r + 1;
//    while (i < j)
//    {
//        do {
//            i++;
//        } while (num[i] > x);
//        do {
//            j--;
//        } while (num[j] < x);
//        if (i < j)
//        {
//            swap(num[i], num[j]);
//        }
//    }
//    quick(num, l, j);
//    quick(num, j + 1, r);
//}
//int main()
//{
//    scanf("%d", &t);
//    while (t--)
//    {
//        scanf("%d", &b);
//        for (int i = 0; i < b; i++)
//        {
//            scanf("%d", &num[i]);
//        }
//        quick(num, 0, b - 1);
//        for (int i = 0; i < b; i++)
//        {
//            printf("%d ", num[i]);
//        }
//    }
//
//}


//#include <iostream>
//using namespace std;
//const int N = 10010;
//int a[N], b[N];
//int main()
//{
//    int n, m, x;
//    cin >> n >> m >> x;
//    for (int i = 0; i < n; i++)
//        scanf("%d", &a[i]);
//    for (int j = 0; j < m; j++)
//        scanf("%d", &b[j]);
//    int i = 0, j = m - 1;
//    while (a[i] + b[j] > x) j--;
//    while (a[i] + b[j] < x) i++;
//    if (a[i] + b[j] == x) printf("%d %d",i,j);
//}



//#include <iostream>
//using namespace std;
//const int N = 10010;
//int a[N], b[N];
//int main()
//{
//	int n, m,x;
//	cin >> n >> m>>x;
//	for (int i = 0; i < n; i++)scanf("%d", &a[i]);
//		for (int i = 0; i < m; i++)scanf("%d", &b[i]);
//		int i = 0, j = m - 1;
//		while (j >= 0&&b[j] + a[i] > x)j--;
//		while (i < n &&b[j] + a[i] < x)i++;
//		if (a[i] + b[j] == x)printf("%d %d", i, j);
//	return 0;
//}



//#include<iostream>
//using namespace std;
//const int N = 10010;
//int main()
//{
//    int n;
//    cin >> n;
//    int t = 0;
//    int f = 0;
//    int g = 0;
//    while (n--)
//    {
//        char c[20];
//        scanf("%s", c);
//        if (!strcmp(c, "CTRL")) 
//        { 
//            t++; 
//            continue;
//        }
//        if (!strcmp(c, "UNCTRL"))
//        {
//            t--;
//            continue;
//        }
//        if (t > 0 && c[0] == 'C')
//        {
//            f++;
//            continue;
//        }
//        if (t > 0 && c[0] == 'V' && f > 0)
//        {
//            g++;
//        }
//    }
//    if (g > 0)printf("Yes");
//    if (g == 0)printf("No");
//    return 0;
//}


//#include<stdio.h>
//int main()
//{
//	int a;
//	scanf("%d", &a);
//	int num[1000];
//	for (int i = 0; i < a; i++)
//		scanf("%d", &num[i]);
//	int t = 0;
//	int s = 0;
//	for (int i = 0; i < a-1; i++)
//	{
//		if (num[i] > num[i + 1])
//		{
//			s++;
//		}
//		else
//		{
//			t = max(t,s+1);
//			s = 0;
//		}
//	}
//	printf("%d", t);
//	return 0;
//}



//int  main()
//{
//	int a = 0;
//	char c1,c2;
//	scanf("%d%c%c", &a,&c1,&c2);
//	int num[10];
//	int i = 0;
//	int sum = 0;
//	while (a)
//	{
//		num[i] = a % 10;
//		sum += num[i];
//		i++;
//		a /= 10;
//	}
//	for (int j = 0; j <=num[i - 1]; j++)
//	{
//		for (int h = 0; h < sum; h++)
//		{
//			printf("%c", c2);
//		}
//		printf("\n");
//	}
//	return 0;
//}



//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int num[100000];
//	for (int i = 0; i < n; i++)
//		scanf("%d", &num[i]);
//	int d = 0;
//	scanf("%d", &d);
//	int x = 0;
//	for (int i = 0; i < n; i++)
//	{
//		if (num[i] == d)
//		{
//			x = i+1;
//			break;
//		}
//	}
//	if (x == 0)
//	{
//		printf("-1");
//		return 0;
//	}
//	printf("%d", x);
//	return 0;
//}



//int main()
//{
//	int a, b;
//	scanf("%d %d", &a, &b);
//	int y;
//	scanf("%d", &y);
//	int num[10] = { 0 };
//	int t = 0;
//	int p = 0;
//	int w = 0;
//	for (int i = a; i <= b; i++)
//	{
//		if (i == 1)
//		{
//			continue;
//		}
//		for (int j = 2; j < i; j++)
//		{
//			if (i % j == 0)
//			{
//				t++;
//				break;
//			}
//		}
//		if (t == 0)
//		{
//			num[p] = i;
//			p++;
//		}
//		t = 0;
//		if (p==3)
//		{
//			break;
//		}
//	}
//	int q = 0;
//	if (p < 2)
//	{
//		for (int i = 0; i < p; i++)
//		{
//			q += num[i];
//		}
//		printf("%d", q);
//	}
//	for (int i = 0; i < p; i++)
//	{
//		printf("%d ", num[i]);
//	}
//	printf("\n");
//	for (int i = 105; i <= y; i+=2)
//	{
//		t = 0;
//		if (i % 3 == 0)
//		{
//			t++;
//		}
//		if (i % 5 == 0)
//		{
//			t++;
//		}
//		if (i % 7 == 0)
//		{
//			t++;
//		}
//		if (i % 11 == 0)
//		{
//			t++;
//		}
//		if (i % 13 == 0)
//		{
//			t++;
//		}
//		if (t >= 2)
//		{
//			printf("%d ", i);
//		}
//	}
//
//	
//	return 0;
//}



//#include<iostream>
//#include<cstring>
//using namespace std;
//#include<algorithm>
//const int N = 510;
//int n, m;
//int g[N][N];
//int dist[N];
//bool st[N];
//int dijkstra()
//{
//	memset(dist, 0x3f, sizeof dist);
//	dist[1] = 0;
//	for (int i = 0; i < n; i++)
//	{
//		int t = -1;
//		for (int j = 1; j <= n; j++)
//			if (!st[j] && (t == -1 || dist[t] > dist[j]))
//				t = j;
//		st[t] = true;
//		for (int j = 1; j <= n; j++)
//			dist[j] = min(dist[j], dist[t]+g[t][j]);
//	}
//	if (dist[n] == 0x3f3f3f3f) return -1;
//	else return dist[n];
//}
//int main()
//{
//	cin >> n >> m;
//	memset(g, 0x3f, sizeof g);
//	while (m--)
//	{
//		int a, b, c;
//		cin >> a >> b >> c;
//		g[a][b] = min(g[a][b], c);
//	}
//	int t = dijkstra();
//	printf("%d\n", t);
//}
//void menu(int a)
//{
//	for (int i = 1; i <= a; i++)
//	{
//		for (int j = 1; j <= i; j++)
//		{
//			printf("%d*%d=%d\t",i,j,i * j);
//		}
//		printf("\n");
//	}
//}
//int main()
//{
//	int a;
//	scanf("%d", &a);
//	menu(a);
//}
//bool judge(int a)
//{
//	int t = 0;
//	for (int i = 1; i < a; i++)
//	{
//		if (a % i == 0)
//		{
//			t++;
//		}
//	}
//	if (t<2)
//		return true;
//	else
//		return false;
//}
//int main()
//{
//	int a;
//	scanf("%d", &a);
//	judge(a);
//	if (judge(a))
//	{
//		printf("Yes");
//	}
//	else
//	{
//		printf("No");
//	}
//}


//int main()
//{
//	int num[10];
//	int max = -999990;
//	for (int i = 0; i < 10; i++)
//	{
//		scanf("%d", &num[i]);
//		if (num[i] > max)max = num[i];
//	}
//	printf("%d", max);
//	return 0;
//}


//#include <iostream>
//#include <string>
//#include <vector>
//using namespace std;
//vector<int> mol(vector<int>A, long long b)
//{
//	int t = 0;
//	vector<int> C;
//	for (int i = 0; i <= A.size() - 1 || t; i++)
//	{
//		if (i < A.size())t += A[i] * b;
//		C.push_back(t % 10);
//		t /= 10;
//	}
//	return C;
//}
//int main()
//{
//	string a;
//	long long b;
//	cin >> a >> b;
//	if (b == 0)
//	{
//		printf("0");
//		return 0;
//	}
//	int x;
//	scanf("%d", &x);
//	vector<int>A, B;
//	for (int i = a.size() - 1; i >= 0; i--)A.push_back(a[i] - '0');
//	auto C = mol(A, b);
//	for (int i = C.size() - 1; i >= 0; i--)
//	{
//		printf("%d", C[i]);
//	}
//	return 0;
//}



//#include<iostream>
//#include<cstring>
//#include<algorithm>
//using namespace std;
//const int m = 10010;
//const int n = 510;
//int n, m, k;
//int dist[n], backup[n];
//struct eadge {
//    int a, b, w;
//}eadge[m];
//int ball_ford()
//{
//    memset(dist, 0x3f, sizeof dist);
//    dist[1] = 0;
//    for (int i = 0; i < k; i++)
//    {
//        memcpy(backup, dist, sizeof dist);
//        for (int j = 0; j < m; j++)
//        {
//            int a = eadge[j].a, b = eadge[j].b, w = eadge[j].w;
//            dist[b] = min(dist[b], backup[a] + w);
//        }
//    }
//    if (dist[n] > 0x3f3f3f3f/ 2) return -1;
//    else  return dist[n];
//}
//int main()
//{
//    scanf("%d %d %d", &n, &m, &k);
//    int a, b, w;
//    for (int i = 0; i < m; i++)
//    {
//        scanf("%d%d%d", &a, &b, &w);
//        eadge[i] = { a,b,w };
//    }
//
//    int t = ball_ford();
//
//    if (t == -1)puts("impossible");
//    else printf("%d\n", t);
//    printf("\n");
//}



//#include <iostream>
//#include <string.h>
//#include<cstring>
//#include <algorithm>
//#include <queue>
//
//using namespace std;
//
//typedef pair<int, int> PII;
//
//const int N = 1e6 + 10;
//
//int n, m;
//
//int dist[N];
//
//int h[N], w[N], e[N], ne[N], idx;
//
//bool sn[N];
//
//void add(int x, int y, int z)
//{
//	w[idx] = z;
//	e[idx] = y;
//	ne[idx] = h[x];
//	h[x] = idx++;
//}
//
//int spfa()
//{
//	memset(dist, 0x3f, sizeof dist);
//	dist[1] = 0;
//	sn[1] = true;
//	queue<int> q;
//	q.push(1);
//	while (q.size())
//	{
//		int t = q.front();
//		q.pop();
//		sn[t] = false;
//		for (int i = h[t]; i != -1; i = ne[i])
//		{
//			int j = e[i];
//			if (dist[j] > dist[t] + w[i])
//			{
//				dist[j] = dist[t] + w[i];
//				if (!sn[j])
//				{
//					q.push(j);
//					sn[j] = true;
//				}
//			}
//		}
//	}
//	if (dist[n] == 0x3f3f3f3f)
//	{
//		return -1;
//	}
//
//	return dist[n];
//}
//
//int main()
//{
//	cin >> n >> m;
//
//	memset(h, -1, sizeof h);
//
//	while (m--)
//	{
//		int a, b, c;
//		cin >> a >> b >> c;
//		add(a, b, c);
//	}
//
//	cout << spfa() << endl;
//
//	return 0;
//}